#include<iostream>
#include<stdlib.h>

using namespace std;
typedef double ElemType;
struct LNode
{
    ELemType data;
    LNode* next;
};
void InitList(LNode* &HL)
{
    HL=NULL;
}
void ClearList(LNode*& HL)
{
    LNode *cp;
    LNode *np;
    cp=HL;
    while(cp!=NULL)
    {
        np=cp->next;
        delete cp;
        cp=np;
    }
    HL=NULL;
}
int LenthList(LNode* HL)
{
    int i=0;
    while(HL!=NULL)
    {
        i++;
        HL->next;
    }
    return i;
}
bool EmptyList(LNode* HL)
{
    return HL==NULL;
}
ElemType GetList(LNode* HL, int pos)
{
    if(pos<1)
    {
        cerr<<"pos is out range!" <<endl;
        exit(1);
    }
    int i=0;
    while(HL!==NULL)
    {
        i++;
        if(i==pos) break;
        HL=HL->next;
    }
    if(HL!=NULL)
        return HL->data;
    else
    {
        cerr<<"pos is out range!"<<endl;
        exit(1);
    }
}
void TraverseList(LNode* HL)
{
    while(HL!=NULL)
    {
        cout<<HL->data<<" ";
        HL=HL->next;
    }
    cout<<endl;
}
bool FindList(LNode* HL, ElemType& item)
{
    while(HL!=NULL)
        if(HL->data==item)
        {
            item=HL->data;
            return true;
        }
        else HL=HL->next;
    return false;
}
bool UpdateList(LNode* HL, const ELemType& item)
{
    while(HL!=NULL)
        if(HL->data==item) break;
        else HL=HL->next;
    if(HL==NULL)  return false;
    else
    {
        HL->data=item;
        return false;
    }
}
bool InsertList(LNode* HL, ELemType item, int pos)
{
    if(pos<-1)
    {
        cout<<"pos值无效！"<<endl;return false;
    }
    LNode* cp=HL;
    LNode* ap=NULL;
    if(pos==0)
    {
        while(cp!=NULL)
        {
            if(item<cp->data) break;
            else
            {
                ap=cp;
                cp=cp->next;
            }
        }
    }
    else if(pos==-1)
        while(cp!=NULL){ap=cp; cp=cp->next;}
    else
    {
        int i=0;
        while(cp!=NULL)
        {
            i++;
            if(i==pos) break;
            else
            {
                ap=cp; cp=cp->next;
            }
        }
        if(cp==NULL && i+1<pos)
        {
            cout<<"pos值超出单链表长度加1！"<<endl;
            return false;
        }
    }
    if(ap==NULL)
    {
        newptr->next=HL;
        HL=newptr;
    }
    else
    {
        newptr->next=cp;
        ap->next=newptr;
    }
    return true;
}
bool DeleteList(LNode* &HL, ELemType& item, int pos)
{
    if(HL==NULL)
    {
        cerr<<"单链表为空，删除操作无效!"<<endl;
        return false;
    }
    if(pos<-1)
    {
        cout<<"pos值无效!"<<endl; return false;
    }
    LNode* cp=HL;
    LNode* ap=NULL;
    if(pos==0)
    {
        while(cp!=NULL)
        {
            if(item==cp->data) break;
            else
            {
                ap=cp;
                cp=cp->next;
            }
        }
        if(cp==NULL)
        {
            cout<<"单链表中没有相应的结点可删除！"<<endl;
            return false;
        }
    }
    else if(pos==-1)
        while(cp->next!=NULL){ap=cp; cp=cp->next;}
    else
    {
        int i=0;
        while(cp!=NULL)
        {
            i++;
            if(i==pos) break;
            else
            {
                ap=cp;
                cp=cp->next;
            }
        }
        if(cp==NULL)
        {
            cout<<"pos值无效!"<<endl; return false;
        }
    }
    if(ap==NULL) HL=HL->next;
    else ap->next=cp->next;
    delete cp;
    return true;
}
void SortList(LNode* &HL)
{
    LNode* SL;
    InitList(SL);
    LNode* r=HL;
    while(r!=NULL)
    {
        LNode* t=r->next;
        LNode* cp=SL;
        LNode* ap=NULL;
        while(cp!=NULL)
        {
            if(r->data<cp->data) break;
            else
            {
                ap=cp;
                cp=cp->next;
            }
        }
        if(ap==NULL)
        {
            r->next=SL;
            SL=r;
        }
        r=t;
    }
    HL=SL;
}
int main()
{
    LNode* a;
    InitList(a);
    ELemType r[5]={1,3,5,10,14};
    int i;
    for(i=5; i>=0; i--)InsertList(a,r[i],i);
    cout<<"线性表长度a:";
    cout<<endl;
    CLearList(a);
}





















































